4.8 KB · ⇊ 2 parts · ⤓ Micron 4.8 KB · ⤓ HTML 32.3 KB

top

Der Itai-Rodeh-Algorithmus ist ein Algorithmus der Las-Vegas Klasse zur Auswahl anonymer unidirektionale Ringe und baut auf dem Chang- und Roberts-Algorithmus auf.

• Voraussetzungen

• Ablauf

• Erste Phase

• Weitere Phasen

• Nachrichtenkomplexität

• Quellen

• unidirektionaler Ring

• Ringgröße (Anzahl der Knoten) n {\displaystyle n} bekannt

Der Algorithmus läuft in Phasen (Wahlgängen) ab.

In der ersten Phase wählen alle Knoten eine zufällige Identifikationsnummer, I D > 0 {\displaystyle \mathrm {ID} >0} . Dann schickt jeder Knoten eine Nachricht bestehend aus eigener ID i {\displaystyle i} , Sprungzähler h {\displaystyle h} (hopcount, gibt an, wie oft die Nachricht weitergeleitet wurde), einem Merker f {\displaystyle f} (flag) und der aktuellen Phase p {\displaystyle p} . Initial gilt h = 1 , f = 1 , p = 1 {\displaystyle h=1,f=1,p=1} .

• wenn eine Nachricht ⟨ ⟨ i , h , f , p ⟩ ⟩ {\displaystyle \langle i,h,f,p\rangle } empfangen wird:

• falls p {\displaystyle p} kleiner ist als die aktuelle Phase beim Empfänger, wird die Nachricht nicht weitergeleitet („verschluckt“ nach Chang und Roberts)

• falls i > I D {\displaystyle i>\mathrm {ID} } wird die Nachricht weitergeleitet als ⟨ ⟨ i , h + 1 , f , p ⟩ ⟩ {\displaystyle \langle i,h+1,f,p\rangle }

• falls i < I D {\displaystyle i<\mathrm {ID} } wird die Nachricht nicht weitergeleitet

• falls i = I D {\displaystyle i=\mathrm {ID} }

• wenn h ≠ ≠ n {\displaystyle h\neq n} wird f {\displaystyle f} auf 0 {\displaystyle 0} gesetzt (der Merker merkt sich, dass die ID mehrfach vergeben ist) und die Nachricht als ⟨ ⟨ i , h + 1 , 0 , p ⟩ ⟩ {\displaystyle \langle i,h+1,0,p\rangle } weitergeleitet

• wenn h = n {\displaystyle h=n} und f = 1 {\displaystyle f=1} hat der Knoten die Auswahl gewonnen (Mitteilung an alle anderen durch eine spezielle Nachricht)

• wenn h = n {\displaystyle h=n} und f = 0 {\displaystyle f=0} gibt es mehrere Gewinner.

Falls es mehrere Gewinner der ersten bzw. vorherigen Phase gibt, dann startet diese Gruppe einen weiteren Durchlauf des Algorithmus mit p = p + 1 {\displaystyle p=p+1} . Der Ablauf ist genau wie in der ersten Phase, jedoch mit verringerter Anzahl der Teilnehmer. Passive Knoten leiten Nachrichten lediglich weiter; lediglich der Sprungzähler h {\displaystyle h} wird dabei erhöht.

Für die erste Phase werden n {\displaystyle n} Nachrichten benötigt. Da die Anzahl der Phasen theoretisch unbegrenzt ist, geht die Nachrichtenkomplexität gegen unendlich. Praktisch ist dieser Fall aber sehr unwahrscheinlich. So kommen für jede weitere Phase weniger als n {\displaystyle n} Nachrichten hinzu.

Der Erwartungswert E {\displaystyle E} für die Anzahl der Wahlgänge (wenn ∀ ∀ I D : I D ∈ ∈ [ 1 , . . . , n ] {\displaystyle \forall ID:ID\in [1,...,n]} ): E ≤ ≤ e ( n n − − 1 ) {\displaystyle E\leq e\left({\frac {n}{n-1}}\right)} ( e {\displaystyle e} ist die Eulersche Zahl)

• Vorlesung Verteilte Systeme an der TU-Berlin

• A. Itai and M. Rodeh. Symmetry breaking in distributed networks, In Proceedings of the 22nd IEEE Symposium on Science, pages 150-158. IEEE Press, 1981.